package main

import (
	"fmt"
)

/**
给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]


链接：https://leetcode-cn.com/problems/permutations

解析:
回溯法
https://www.youtube.com/watch?v=43w8tXWKSLw&t=920s
*/
func main() {
	res := permute([]int{1, 2, 3})
	fmt.Println(res)
}

func permute(nums []int) [][]int {
	res := [][]int{}
	list := []int{}
	m := make(map[int]bool)
	helper(&res, nums, list, m)
	return res
}

func helper(res *[][]int, nums []int, list []int, m map[int]bool) {
	if len(list) == len(nums) {
		tmp := make([]int, len(nums))
		copy(tmp, list)
		*res = append(*res, tmp)
		return
	} else {
		for i := 0; i < len(nums); i++ {
			if _, ok := m[i]; !ok {
				m[i] = true
				list = append(list, nums[i])
				helper(res, nums, list, m)
				delete(m, i)
				list = list[:len(list)-1]
			}
		}
	}
}
